package vip.zhenzicheng.algorithm.leetcode.stack_queue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/decode-string/">字符串解码 [中等]</a>
 * <pre>
 * 给定一个经过编码的字符串，返回它解码后的字符串。<br/>
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像  3a  或  2[4]  的输入。
 * <br/>
 * 示例 1：
 *    输入：s = "3[a]2[bc]"
 *    输出："aaabcbc"
 * 示例 2：
 *    输入：s = "3[a2[c]]"
 *    输出："accaccacc"
 * 示例 3：
 *    输入：s = "2[abc]3[cd]ef"
 *    输出："abcabccdcdcdef"
 * 示例 4：
 *    输入：s = "abc3[cd]xyz"
 *    输出："abccdcdcdxyz"
 * <br/>
 * 提示：
 * 1 <= s.length <= 30
 * s  由小写英文字母、数字和方括号  '[]' 组成
 * s  保证是一个  有效  的输入。
 * s  中所有整数的取值范围为  [1, 300]
 * </pre>
 *
 * @author zhenzicheng
 * @date 2022-06-11 14:17
 */
public class DecodeString_394 {
  int i = 0; // 遍历字符串的下标
  StringBuilder result = new StringBuilder();
  Deque<String> queue = new ArrayDeque<>(); // 作为缓冲，模拟队列

  public static void main(String[] args) {
    DecodeString_394 e = new DecodeString_394();
    String x = "3[a]2[bc]";
    System.out.println(e.decodeString(x));
  }

  // 处理数字
  private String getDigit(String s) {
    StringBuilder sb = new StringBuilder();

    while (Character.isDigit(s.charAt(i))) { // 只要c还是数字，就都存
      sb.append(s.charAt(i++)); // 每次读取数字后，移动全局下标
    }
    return sb.toString();
  }

  private String getStrFromQueue() {
    StringBuilder sb = new StringBuilder();
    while (!queue.isEmpty()) {
      sb.append(queue.poll());
    }
    return sb.toString();
  }

  private String appendResult(int repeat, String str) {
    StringBuilder sb = new StringBuilder();
    while (repeat-- > 0) {
      sb.append(str);
    }
    return sb.toString();
  }

  public String decodeString(String s) {
    int len = s.length();
    Deque<String> stack = new ArrayDeque<>(); // 新版的增强deque当做栈，但是不能保存null

    while (i < len) {
      char c = s.charAt(i); // 当前字符

      if (Character.isDigit(c)) {
        String num = getDigit(s); // 获取完整数字
        stack.push(num);
      } else if ('[' == c || Character.isLetter(c)) {
        stack.push(String.valueOf(c));
        i++;
      } else if (']' == c) {
        String ss;
        while (!(ss = stack.pop()).equals("[")) {
          queue.push(ss);
        }
        String str = getStrFromQueue(); // 从缓存队列中获取所有的字符串拼接结果
        int n = Integer.parseInt(stack.pop()); // 获取前一个数字
        String strs = appendResult(n, str); // 缓存结果
        stack.push(strs); // 放入结果
        i++;
      }
    }

    while (!stack.isEmpty()) {
      result.append(stack.pollLast());
    }

    return result.toString();
  }
}
